package lastRemaining;

import java.util.LinkedList;

public class Solution {
    public int lastRemaining(int n, int m) {
//        int[] arr = new int[m];
//        LinkedList<Integer>list = new LinkedList<>();
//        for (int i = 0; i < n; i++) {
//            list.add(i);
//        }
//        int start = 0;
//        int deleted = (m-1)%list.size();
//        while(list.size()>1){
//            list.remove(deleted);
//            //   System.out.println(start+" "+deleted);
//            start = deleted%list.size();
//            deleted = (start + m-1)%list.size();
//        }
//        return list.get(0);
        // n = 5 m = 3
        // 0 1 2 3 4
        // 移除 index == (0+2)%5 == 2
        // 0 1 3 4
        // 移除 index == (2+2)%4 == 0
        // 1 3 4
        // 移除 index == (0+2)%3 == 2
        // 1 3
        // 移除 index == (4+2)%2 == 0

        // 动态规划
        return f(n,m);
    }
    private int f(int n,int m){
        if(n==1){
            return 0;
        }
        int x = f(n-1,m);
        return (m+x)%n;
    }
}
//class Solution {
//    public int lastRemaining(int n, int m) {
//        return f(n, m);
//    }
//
//    public int f(int n, int m) {
//        if (n == 1) {
//            return 0;
//        }
//        int x = f(n - 1, m);
//        return (m + x) % n;
//    }
//}

